UnivTrevesV1, LNCS, Analysis, bibRecord, 000212

Automatic Complexity Analysis

Identifieur interne : 000212 ( LNCS/Analysis ); précédent : 000211; suivant : 000213

Automatic Complexity Analysis

Auteurs : Flemming Nielson [Danemark] ; Hanne Riis Nielson [Danemark] ; Helmut Seidl [Allemagne]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2002.

RBID : ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28

Descripteurs français

Pascal (Inist)
- Analyse automatique, Analyse programme, Clause Horn, Comportement asymptotique, Matrice creuse.

English descriptors

KwdEn :
- Asymptotic behavior, Automatic analysis, Horn clauses, Program analysis, Sparse matrix.

Abstract

Abstract: We consider the problem of automating the derivation of tight asymptotic complexity bounds for solving Horn clauses. Clearly, the solving time crucially depends on the “sparseness” of the computed relations. Therefore, our asymptotic runtime analysis is accompanied by an asymptotic sparsity calculus together with an asymptotic sparsity analysis. The technical problem here is that least fixpoint iteration fails on asymptotic complexity expressions: the intuitive reason is that O(1)+ srO(1) = O(1) but O(1) + ⋯ + O(1) may return any value.

Url:

https://api.istex.fr/document/EB7186CC090D19320A84864F0CB4065CC4B95D28/fulltext/pdf

DOI: 10.1007/3-540-45927-8_18

Affiliations:

Allemagne, Danemark

Links to Exploration step

ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Automatic Complexity Analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28</idno>
<date when="2002" year="2002">2002</date>
<idno type="doi">10.1007/3-540-45927-8_18</idno>
<idno type="url">https://api.istex.fr/document/EB7186CC090D19320A84864F0CB4065CC4B95D28/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001112</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001112</idno>
<idno type="wicri:Area/Istex/Curation">001001</idno>
<idno type="wicri:Area/Istex/Checkpoint">000B72</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000B72</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Nielson F:automatic:complexity:analysis</idno>
<idno type="wicri:Area/Main/Merge">001F12</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:02-0318071</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000D48</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000188</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000B22</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000B22</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Nielson F:automatic:complexity:analysis</idno>
<idno type="wicri:Area/Main/Merge">001F87</idno>
<idno type="wicri:Area/Main/Curation">001C63</idno>
<idno type="wicri:Area/Main/Exploration">001C63</idno>
<idno type="wicri:Area/LNCS/Extraction">000212</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Automatic Complexity Analysis</title>
<author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
<affiliation wicri:level="1"><country xml:lang="fr">Danemark</country>
<wicri:regionArea>Informatics and Mathematical Modelling, The Technical University of Denmark, DK-2800, Kongens Lyngby</wicri:regionArea>
<wicri:noRegion>Kongens Lyngby</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Danemark</country>
</affiliation>
</author>
<author><name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
<affiliation wicri:level="1"><country xml:lang="fr">Danemark</country>
<wicri:regionArea>Informatics and Mathematical Modelling, The Technical University of Denmark, DK-2800, Kongens Lyngby</wicri:regionArea>
<wicri:noRegion>Kongens Lyngby</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Danemark</country>
</affiliation>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV — Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
<wicri:noRegion>54286, Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2002</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">EB7186CC090D19320A84864F0CB4065CC4B95D28</idno>
<idno type="DOI">10.1007/3-540-45927-8_18</idno>
<idno type="ChapterID">18</idno>
<idno type="ChapterID">Chap18</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Asymptotic behavior</term>
<term>Automatic analysis</term>
<term>Horn clauses</term>
<term>Program analysis</term>
<term>Sparse matrix</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Analyse automatique</term>
<term>Analyse programme</term>
<term>Clause Horn</term>
<term>Comportement asymptotique</term>
<term>Matrice creuse</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We consider the problem of automating the derivation of tight asymptotic complexity bounds for solving Horn clauses. Clearly, the solving time crucially depends on the “sparseness” of the computed relations. Therefore, our asymptotic runtime analysis is accompanied by an asymptotic sparsity calculus together with an asymptotic sparsity analysis. The technical problem here is that least fixpoint iteration fails on asymptotic complexity expressions: the intuitive reason is that O(1)+ srO(1) = O(1) but O(1) + ⋯ + O(1) may return any value.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>Danemark</li>
</country>
</list>
<tree><country name="Danemark"><noRegion><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
</noRegion>
<name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name>
<name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
<name sortKey="Nielson, Hanne Riis" sort="Nielson, Hanne Riis" uniqKey="Nielson H" first="Hanne Riis" last="Nielson">Hanne Riis Nielson</name>
</country>
<country name="Allemagne"><noRegion><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
</noRegion>
<name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000212 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000212 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    LNCS
   |étape=   Analysis
   |type=    RBID
   |clé=     ISTEX:EB7186CC090D19320A84864F0CB4065CC4B95D28
   |texte=   Automatic Complexity Analysis
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

Serveur d'exploration sur l'Université de Trèves

Automatic Complexity Analysis

Automatic Complexity Analysis

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.